package com.leetcode.stack_queue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/24 21:17
 */
public class NextGreaterElements_503 {

    public int[] nextGreaterElements2(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        int max = Integer.MIN_VALUE;
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * len - 1; i++) {
            int j = i % len;
            int now = nums[j];
            max = Math.max(now, max);
            while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
                int temp = stack.pop();
                if (nums[temp] < now) {
                    ans[temp] = now;
                }
            }
            stack.push(j);
        }
        return ans;
    }

    public int[] nextGreaterElements(int[] nums) {
        final int len = nums.length;
        final int[] res = new int[len];
        final Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * len; i++) {
            int j = i % len;
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
                stack.pop();
            }
            // 因为是环形的，所以一定会出现小序号在大序号就在前面的情况
            res[j] = stack.isEmpty() ? -1 : nums[stack.peek()];
            stack.push(j);
        }
        return res;
    }

}
